1. Field of the Invention
This invention relates generally to data communication systems and more specifically to an improved echo cancellation method and apparatus for use in high speed full-duplex data transceiver systems which combines frequency-domain and time-domain echo emulation and frequency-domain adaptive updating.
2. Brief Description of the Prior Art
Full-duplex data transmission is the transmission of data in opposite directions simultaneously over overlapping frequency bands. Echo is the undesired leakage of a transmitted signal into the co-located receiver, superimposed upon and thus interfering with the intended transmission. As an example, in a telephone network, one type of echo occurs when a customer's transmitted signal leaks through the hybrid circuit back into that customer's receiver, interfering with the transmitted signal from another customer.
In the example shown in FIG. 1, the hybrid connector is the 'echo channel' whose operation can be modelled by a finite set of parameters derived by sampling the echo channel response. An echo canceller operates by first estimating the echo parameters, and then linearly convolving the estimate with the transmitted data, thus emulating the echo. This emulated echo is then subtracted from the received signal, which ideally results in an echo-free transmission.
Echo occurs primarily because of mismatched impedances at the hybrid connectors. Because the impedances of the transmission lines are time-varying as well as line-dependent, the echo canceller must be adaptive--it must learn the echo characteristics and track time-varying changes. The echo canceller can be made adaptive as follows: After estimating the echo parameters, emulating the echo, and subtracting it from the received signal, the remaining signal (which contains some residual echo) is fed back and used to update the estimated set of echo parameters. This feedback loop allows the echo canceller to converge to a close approximation of the echo parameters. A basic tutorial on echo cancellation can be found in Digital Communications, E.A. Lee and D.G. Messerschmitt, Kluwer, Boston, 1988.
Echo cancellation may be accomplished either in the time-domain or in the frequency-domain. In time-domain echo cancellation, echo parameters are derived by sampling the echo channel response, and echo emulation involves a complex time-domain convolution. In frequency-domain echo cancellation, the echo parameters are obtained by sampling the spectrum of the echo channel rather than sampling the echo channel response. Echo emulation and adaptive update can then take place in the frequency-domain, using the estimate of the spectrum of the echo channel.
Multicarrier modulation is a means of transmitting data by first grouping the binary digital data to be transmitted into sub-blocks. The sub-blocks are then further grouped into fixed-length blocks. As an example, each sub-block may contain one to eight bits, and 100 sub-blocks will form a block. For analog transmission across the communication channel, a set of carrier signals is used whose frequencies lie at evenly spaced values across the usable frequency band. This set of carrier signals is equal in number to the number of sub-blocks within a block. Continuing the above example, with a sampling frequency of 1.0 MHz, 100 carrier signals would be used at multiples of 10 kHz. The bits within each sub-block are then used to modulate the corresponding carrier signal. The set of modulated carriers are then added together, and the resultant signal is transmitted across the channel. Multicarrier modulation is described more fully in "Multicarrier Modulation for Data Transmission: An Idea whose Time Has Come", J.A.C. Bingham, IEEE Communications Magazine, 28(5):5-14, May 1990.
Discrete Multitone Modulation (DMT) is a form of multicarrier modulation that is implemented with digital signal processing, where an IFFT/FFT pair are used as modulation/demodulation vectors. DMT is discussed in detail in "Discrete Multiple Tone Modulation with Coset Coding for the Spectrally Shaped Channel", A. Ruiz, J.M. Cioffi, and S. Kasturia, IEEE Transactions on Communications, 40:1012-29, June 1992.
Digital communication systems rely upon four basic time and frequency-domain relationships that can be found in any basic digital signal processing text, such as Discrete-Time Signal Processing, A.V. Oppenheim and R.W. Schafer, Prentice-Hall, Englewood Cliffs, NJ, 1989. These relationships are enumerated below:
1. Cyclic convolution: The cyclic convolution of two equally-sized time-domain sequences is equivalent to the block multiply of their FFT's.
2. Interpolation: Padding a discrete sequence with k zeros between each sample is equivalent to replicating the FFT of the sequence k times.
3. Decimation: If the copies of the spectra of a discrete sequence are spaced by multiples of 1 Mhz, down-sampling the discrete sequence by 10 spaces the spectra by multiples of 100 Khz. If the spectrum bandwidth is greater than 100 kHz, then aliasing occurs.
4. Time-delay: Time delay in the time domain is equivalent to exponential weighting in the frequency domain.
In general an echo channel is formed by multiplying together the responses of the DAC, the transmit filter, the hybrid, the anti-aliasing filter, and the ADC, as explained in Discrete-Time Signal Processing, A.V. Oppenheim and R.W. Schafer, Prentice-Hall, Englewood Cliffs, NJ, 1989. These five operations and some of their ramifications for echo cancellation are described below.
The DAC converts the sequence x(n) to an impulse train multiplied by a continuous time function x(t), and convolves this with the impulse response of a zero-order hold (ZOH). In the frequency-domain, this corresponds to replicating the spectrum of X(f) at multiples of the sampling rate 1/T (denoted as X.sub.p (f)), multiplied by one copy of a sinc function.
Ideally, the transmit, or reconstruction filter, T(f), should cut off at around 1/2T. Otherwise, there are frequency components outside this bandwidth, and the echo canceller must cancel these components as well. We denote the hybrid frequency-domain response by H(f). The anti-aliasing filter, A(f), ideally cuts off at 1/2T'.
The ADC is a sample and hold, so that the spectra are now replicated at multiples of the sampling rate 1/T', and multiplied by a sinc. If the anti-aliasing filter is not ideal, then aliasing occurs, and these effects must be modelled by the echo canceller.
The effective echo channel impulse response is the frequency-domain product of these five responses: EQU H.sub.O (f)=X.sub.p (f)T(f)H(f)A(f)sinc.sup.2 (f)
When T&gt;T', the width of A(f) exceeds the width of T(f), so the effects of T(f) dominate, and out-of-band noise is a consideration. When T'&gt;T, the width of T(f) exceeds the width of A(f), so the effects of A(f) dominate, and aliasing is a consideration.
As explained in "Asynchronous and Timing Jitter Insensitive Data Echo Cancellation", D.G. Messerschmitt, IEEE Transactions on Communications, 34:1209-1217, December 1986, the timing signal on the customer end is derived from the received signal by means of a timing recovery circuit, and is used by both the analog-to-digital converter (ADC) for sampling the output of the hybrid as well as the transmitter for clocking the transmit data symbols. Timing jitter is phase jitter in the timing signal, and can significantly degrade performance of the echo canceller. However, timing jitter can be thought of as a delay in time, and a delayed block of time-domain symbols corresponds to a frequency-domain multiplication of the FFT of the non-delayed block of data symbols with a linear phase filter. Therefore, timing-phase jitter can be compensated for by a frequency-domain block multiplication of the jittered block with the settings of the inverse of the linear phase filter, leaving the unjittered block.
Most existing echo cancellers use the tapped-delay line structure (also known as an FIR filter) to model the echo channel and replicate the echo. However, at high data rates, the FIR filter can be several hundred taps long, and the computational complexity is high. Our invention avoids this complexity by performing the bulk of echo emulation in the frequency-domain.
Previous work on echo cancellation with multicarrier modulation has been done by J. Yang, S. Roy, and N.H. Lewis in "Data Driven Echo Cancellation for A Multi-Tone Modulation System", to appear in IEEE Transactions on Communications, 1992. This work contains three time-domain filters for each subchannel.
Previous work has also been done by J.M. Cioffi and J. Bingham in "A Data-Driven Multitone Echo Cancellor", Globecom '91, pages 57-61, Phoenix, Ariz., January 1991. This work contains two echo cancellers: a computationally expensive signal-driven time-domain echo canceller and an adaptive data-driven frequency-domain echo canceller. The time-domain echo canceller is significantly more complex than that in the present invention. Furthermore, Cioffi and Bingham's work contains neither the present invention's timing jitter correction, nor the present invention's applicability to asymmetric data transmission.
The standard mathematical model for echo generation is a discrete-time linear convolution of a portion of the previous data symbol concatenated with the current data symbol and the echo finite impulse response (FIR) taps (FIG. 2(a)). It is assumed that the echo response has been sampled at twice the Nyquist rate. However, the same results can be achieved with the sum of a cyclic convolution, depicted by an "X", and a linear convolution, depicted by an "*" (FIG. 2(b)). Note that the larger the cyclic prefix, the smaller the two data sequences for the linear convolution. Combining a cyclic convolution with a linear convolution has the advantage that the cyclic convolution can be performed faster in the frequency-domain with a block multiply. The short linear convolution is performed in the time-domain.